package main

import (
	"fmt"
	util "go-algorithm-practice/0_util"
)

// 二分查找
func BinarySearch(arr []int, target int) int {
	if arr == nil || len(arr) == 0 {
		return -1
	}
	left := 0
	right := len(arr) - 1
	for left <= right {
		mid := left + ((right - left) >> 1)
		if arr[mid] > target {
			right = mid - 1
		} else if arr[mid] < target {
			left = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

// 找到数组内>=target的最左下表
func LeftBinarySearch(arr []int, target int) int {
	res := -1
	if arr == nil || len(arr) == 0 {
		return res
	}
	left := 0
	right := len(arr) - 1
	for left <= right {
		mid := left + ((right - left) >> 1)
		if arr[mid] >= target {
			res = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return res
}

// 局部最小值问题
func PartMin(arr []int) int {
	if arr == nil || len(arr) == 0 {
		return -1
	}
	if len(arr) == 1 || arr[0] < arr[1] {
		return 0
	}
	if arr[len(arr)-1] < arr[len(arr)-2] {
		return len(arr) - 1
	}

	left := 1
	right := len(arr) - 2

	for left < right {
		mid := left + ((right - left) >> 1)
		if arr[mid] > arr[mid-1] {
			right = mid - 1
		} else if arr[mid] > arr[mid+1] {
			left = mid + 1
		} else {
			return mid
		}
	}
	return left

}

func main() {
	fmt.Println(BinarySearch([]int{20, 31, 31, 36, 36, 40, 46, 78, 90, 90}, 36))

	fmt.Println(LeftBinarySearch([]int{20, 31, 31, 36, 36, 40, 46, 78, 90, 90}, 36))

	for i := 0; i < 100; i++ {
		fmt.Println("res: ", PartMin(util.RandomArray(100)))
	}

	fmt.Println(PartMin([]int{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}))
}
